package com.leetcode.普通数组;

//除自身以外数组的乘积
public class lc_238 {
    public static void main(String[] args) {

    }

    //给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
    //不得使用除法,且在 O(n) 时间复杂度内完成此题
    public int[] productExceptSelf(int[] nums) {
        //思路:对于第i个数,求出左边的乘积和右边的乘积
        //1.定义nums长度len,分别定义第i位左边,右边的乘积,定义结果数组
        int len = nums.length;
        int[] left = new int[len];
        int[] right = new int[len];
        int[] res = new int[len];

        //2.遍历得到左边乘积,第0位乘1, 第一位乘nums[0]
        left[0] = 1;
        for (int i = 1; i < len; i++) {
            left[i] = nums[i - 1] * left[i - 1];
        }

        //3.遍历得到右边乘积,第len-1位乘1, 第len-2位乘nums[len-1]
        right[len - 1] = 1;
        for (int i = len - 2; i >= 0; i--){
            right[i] = nums[i + 1] * right[i + 1];
        }

        //4.遍历得到结果数组,对于第i位,结果位left[i]*right[i]
        for (int i = 0; i < len; i++){
            res[i] = left[i] * right[i];
        }

        return res;
    }
}
